/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package util;

import saphre.core.Store; 
import saphre.core.SuffixArray;
import util.sorting.Multiset;

import java.util.Set;
import java.util.TreeSet;
import java.io.Serializable;


/**
 * A class representing an lcp-interval.
 * 
 * @author Dale Gerdemann
 */
public class Interval implements Comparable<Interval>, Serializable {

    public static Store store;
    
    //left boundary of interval
    int lb;
    
    //right boundary of interval
    int rb;
    static Interval empty = new Interval();

    /**
     * Construct a new interval with a left boundary and a right boundary.
     * @param lb
     * @param rb 
     */
    public Interval(int lb, int rb) {
        this.lb = lb;
        this.rb = rb;
    }

    public Interval() {
        this.lb = 0;
        this.rb = -1;
    }

    /**
     * Get the left boundary.
     * @return 
     */
    public int lb() {
        return lb;
    }

    /**
     * Get the right boundary.
     * @return 
     */
    public int rb() {
        return rb;
    }

    /**
     * Get the midpoint of an lcp-interval.
     * @param cldtab
     * @return 
     */
    public int mid(int[] cldtab) {
        int mid = cldtab[lb];
        if (mid <= lb || mid > rb) {
            mid = cldtab[rb];
        }
        return mid;
    }

    /**
     * Check if it is a trivial interval.
     * @return true if interval is of length 1 
     */
    public boolean trivial() {
        return lb == rb;
    }

    /**
     * Check if it is a non-trivial interval.
     * @return true if interval is not length 1
     */
    public boolean nonTrivial() {
        return lb != rb;
    }

    /**
     * Check if interval does not exist.
     * @return true if interval is of length 0
     */
    public boolean empty() {
        return rb < lb;
    }

    /**
     * Get term frequency of the interval.
     * @return the term frequency for the interval
     */
    public int tf() {
        return rb - lb + 1;
    }

    // Naive method for document frequency. Doubles the running time
    // of td (top down interval tree traversal). But this is not a
    // major problem since td is so fast. The real bottlenecks are
    // extendend suffix array construction, and especially
    // construction of the new child table. Still the plan is to
    // improve this for a future version.
    /**
     * Get the document frequency for this interval.
     * @return the document frequency for the interval
     */
    public int df(SuffixArray sa, Store store) {
        Set<Integer> d = new TreeSet<Integer>();
        for (int i = lb; i <= rb; i++) {
            d.add(store.docNum(sa.suftab[i]));
        }
        return d.size();
    }

    /**
     * Get the document distribution for this interval.
     * @return the document distribution for the interval
     */
    public Multiset docDist(SuffixArray sa, Store store) {
        Multiset d = new Multiset();
        for (int i = lb; i <= rb; i++) {
            d.incr(store.docNum(sa.suftab[i]));
        }
        return d;
    }

    /**
     * Get the alphabet for the interval.
     * @return the "alphabet" for the interval. An interval represents a
     * sequence of suffixes. The "alphabet" is the set containing the first
     * letter of each of these suffixes.
     */
    public int[] alpha(SuffixArray sa, Store store) {
        int[] result = new int[alphaSize(sa)];
        int lcp = sa.getLcp(this);
        alpha1(this, sa, lcp, store, result, 0);
        return result;
    }

    /*
     * Helper to get the alphabet for an interval.
     */
    private static int alpha1(Interval inter, SuffixArray sa, int lcp,
            Store store, int[] result, int idx) {
        if (inter.trivial()) {
            result[idx] = store.text[sa.suftab[inter.lb] + lcp];
            return idx + 1;
        } else {
            int mid = sa.cldtab[inter.lb];
            if (mid <= inter.lb || mid > inter.rb) {
                mid = sa.cldtab[inter.rb];
            }
            if (lcp < sa.lcptab[mid]) {
                result[idx] = store.text[sa.suftab[inter.lb] + lcp];
                return idx + 1;
            } else {
                Interval left = new Interval(inter.lb, mid - 1);
                Interval right = new Interval(mid, inter.rb);
                int idx1 = alpha1(left, sa, lcp, store, result, idx);
                int idx2 = alpha1(right, sa, lcp, store, result, idx1);
                return idx2;
            }
        }
    }

    /**
     * Get the size of an interval's alphabet.
     * @return the size of the "alphabet" for the interval
     */
    public int alphaSize(SuffixArray sa) {
        int lcp = sa.getLcp(this);
        return alphaSize1(this, sa, lcp);
    }

    /*
     * Helper to get the size of an interval's alphabet.
     */
    private static int alphaSize1(Interval inter, SuffixArray sa, int lcp) {
        if (inter.trivial()) {
            return 1;
        } else {
            int mid = sa.cldtab[inter.lb];
            if (mid <= inter.lb || mid > inter.rb) {
                mid = sa.cldtab[inter.rb];
            }
            if (lcp < sa.lcptab[mid]) {
                return 1;
            } else {
                Interval left = new Interval(inter.lb, mid - 1);
                Interval right = new Interval(mid, inter.rb);
                return alphaSize1(left, sa, lcp)
                        + alphaSize1(right, sa, lcp);
            }
        }
    }

    /**
     * Generate an empty interval.
     * @return an empty interval. Can be used as return value for search miss.
     */
    public Interval before() {
        return new Interval(lb, lb - 1);
    }

    /**
     * Generate an empty interval.
     * @return empty interval. Can be used as return value for search miss.
     */
    public Interval after() {
        return new Interval(rb + 1, rb);
    }

    /**
     * Compare this interval to another one.
     * @param other
     * @return 
     */
    @Override
    public int compareTo(Interval other) {
        if (lb < other.lb) {
            return -1;
        } else if (lb > other.lb) {
            return 1;
        } else if (rb < other.rb) {
            return -1;
        } else if (rb > other.rb) {
            return 1;
        } else {
            return 0;
        }
    }

    /**
     * Check if two intervals are equal.
     * @param other
     * @return 
     */
    public boolean equals(Interval other) {
        return (other != null) && lb == other.lb && rb == other.rb;
    }

    /**
     * Check if this interval is contained within the other interval.
     * @param other the other interval
     * @return 
     */
    public boolean contains(Interval other) {
        return lb <= other.lb && rb >= other.rb;
    }

    /**
     * Get a string representation of this interval.
     * @return 
     */
    @Override
    public String toString() {
        if (empty()) {
            return "_";
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append("(").append(lb).append(",");
            sb.append(rb).append(")");
            return sb.toString();
        }
    }

    /**
     * Check if this interval represents a palindrome.
     * @param sa
     * @param store
     * @return 
     */
    public boolean isPalindrome(SuffixArray sa, Store store) {
        int[] s = toArray(sa, store);
        int lo = 0;
        int hi = s.length - 1;

        if (s.length != 4) {
            return false;
        }
        //        if (s[0] != s[1]) return false;
        //if (s[2] != s[3]) return false;
        boolean result = true;
        while (lo < hi) {
            if (s[lo++] != s[hi--]) {
                result = false;
                break;
            }
        }
        String phr = toString();
        lo = 0;
        hi = phr.length() - 1;
        if (!result && phr.matches(".*\\p{L}.*\\p{L}.*\\p{L}.*")) {
            while (lo < hi) {
                while (!("" + phr.charAt(lo)).matches("\\p{L}")) {
                    lo++;
                }
                while (!("" + phr.charAt(hi)).matches("\\p{L}")) {
                    hi--;
                }
                if (lo >= hi) {
                    break;
                }
                if (phr.charAt(lo++) != phr.charAt(hi--)) {
                    return false;
                }
            }
        }
        return result;
    }

    /**
     * Get a string representation of this interval. 
     * Overload toString()
     * @param sa
     * @param store
     * @return
     */
    public String toString(SuffixArray sa, Store store) {
        int lcp = sa.getLcp(this);
        //System.out.println(this+" "+ lcp);
        int loc = sa.getSuftab()[lb];
        return store.toStringL(loc, lcp);
    }

    /**
     * Get a string representation of this interval.
     * Overload toString()
     * @param sa
     * @param store
     * @param remove
     * @return 
     */
    public String toString(SuffixArray sa, Store store, int remove) {
        int lcp = sa.getLcp(this);
        //System.out.println(this+" "+ lcp);
        int loc = sa.getSuftab()[lb];
        return store.toStringL(loc + remove, lcp - remove);
    }

    /**
     * Convert this interval to an array representation.
     * @param sa
     * @param store
     * @param remove
     * @return 
     */
    public int[] toArray(SuffixArray sa, Store store, int remove) {
        int lcp = sa.getLcp(this);
        //System.out.println(this+" "+ lcp);
        int loc = sa.getSuftab()[lb];
        return store.toArrayL(loc + remove, lcp - remove);
    }

    /**
     * 
     * @param pa
     * @param store
     * @return 
     */
    public String toRevString(SuffixArray pa, Store store) {
        int lcp = pa.getLcp(this);
        int loc = pa.getSuftab()[lb];
        return store.toStringLRev(loc, lcp);
    }

    /**
     * 
     * @param pa
     * @param store
     * @param depth
     * @param width
     * @return 
     */
    public String toRevString(SuffixArray pa, Store store, int depth, int width) {
        int lcp = pa.getLcp(this);
        int loc = pa.getSuftab()[lb];
        String s = store.toStringLRev(loc, lcp);
        if (s.length() > width) {
            return s;
        }
        String f = "%" + (3 * depth) + "s";
        return String.format(f, s);
    }

    /**
     * 
     * @param sa
     * @param store
     * @return 
     */
    public int[] toArray(SuffixArray sa, Store store) {
        int lcp = sa.getLcp(this);
        int loc = sa.getSuftab()[lb];
        return store.toArrayL(loc, lcp);
    }

    /**
     * 
     * @param pa
     * @param store
     * @return 
     */
    public int[] toRevArray(SuffixArray pa, Store store) {
        int lcp = pa.getLcp(this);
        int loc = pa.getSuftab()[lb];
        return store.toArrayLRev(loc, lcp);
    }

    /**
     * 
     * @param mid
     * @param lcpTable
     * @return 
     */
    public int lcp(int mid, int[] lcpTable) {
        return lcpTable[mid];
    }

    /**
     * 
     * @param suffixTable
     * @return 
     */
    public int pos(int[] suffixTable) {
        return suffixTable[lb];
    }

    /**
     * 
     * @param mid
     * @return 
     */
    public Interval left(int mid) {
        return new Interval(lb, mid - 1);
    }

    /**
     * 
     * @param mid
     * @return 
     */
    public Interval right(int mid) {
        return new Interval(mid, rb);
    }

    /**
     * 
     * @param lcp
     * @param sa
     * @param text
     * @return 
     */
    public Multiset following(int lcp, SuffixArray sa, int[] text) {
        Multiset result = new Multiset();
        //  int lcp = lcp(mid, sa.lcptab);
        int tf = rb - lb + 1;
        int cutoff = tf / 20;
        int prev = text[sa.getSuftab()[lb] + lcp];
        int count = 1;
        for (int i = lb + 1; i <= rb; i++) {
            int next = text[sa.getSuftab()[i] + lcp];
            if (next == prev) {
                count++;
            } else {
                if (count >= cutoff) {
                    result.insert(prev, count);
                }
                count = 1;
                prev = next;
            }
        }
        if (count >= cutoff) {
            result.insert(prev, count);
        }
        return result;
    }

    /**
     * 
     * @param lcp
     * @param sa
     * @param text
     * @return 
     */
    public Multiset preceeding(int lcp, SuffixArray sa, int[] text) {
        Multiset result = new Multiset();
        //        int lcp = lcp(mid, sa.lcptab);
        int tf = rb - lb + 1;
        int cutoff = tf / 20;
        int prev = text[sa.getSuftab()[lb] - 1];
        int count = 1;
        for (int i = lb + 1; i <= rb; i++) {
            int next = text[sa.getSuftab()[i] - 1];
            ;
            if (next == prev) {
                count++;
            } else {
                if (count >= cutoff) {
                    result.insert(prev, count);
                }
                count = 1;
                prev = next;
            }
        }
        if (count >= cutoff) {
            result.insert(prev, count);
        }
        return result;
    }

    /**
     * Check if this interval has left variability.
     * @param lcp
     * @param sa
     * @param text
     * @return 
     */
    public boolean leftVariation(int lcp, SuffixArray sa, int[] text) {
        int left = text[sa.getSuftab()[lb] - 1];
        for (int i = lb + 1; i <= rb; i++) {
            if ((sa.getSuftab()[i] - 1) != left) {
                return true;
            }
        }
        return false;
    }

    /**
     * 
     * @param lcp
     * @param sa
     * @param text
     * @return 
     */
    public int last(int lcp, SuffixArray sa, int[] text) {
        //int lcp = lcp(mid, sa.lcptab);
        return text[sa.getSuftab()[lb] + lcp - 1];
    }

    /**
     * 
     * @param binBWTable
     * @param mid
     * @return 
     */
    public int singleton(int[] binBWTable, int mid) {
        return binBWTable[mid];
    }
}
